<!DOCTYPE HTML>
<html lang="zh-Hans" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>数据库表达式执行的黑魔法：GAT实现引用类型关联 Part 1 - Rust 优秀博文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">
        <link rel="stylesheet" href="../../css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">1.</strong> 类型系统</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../01_类型系统/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow.html"><strong aria-hidden="true">1.1.</strong> Rust Concept Clarification Deref vs AsRef vs Borrow vs Cow</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow/Deref_AsRef_Borrow_Cow释义.html"><strong aria-hidden="true">1.2.</strong> Deref AsRef Borrow Cow 释义</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然/Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然.html"><strong aria-hidden="true">1.3.</strong> Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust的Cow类型有什么用？详解Cow及其用途/Rust的Cow类型有什么用？详解Cow及其用途.html"><strong aria-hidden="true">1.4.</strong> Rust的Cow类型有什么用？详解Cow及其用途</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/判别Fn、FnMut、FnOnce的标准/判别Fn、FnMut、FnOnce的标准.html"><strong aria-hidden="true">1.5.</strong> 判别Fn、FnMut、FnOnce的标准</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/一行代码告诉你内部可变性的真相(UnsafeCell)/一行代码告诉你内部可变性的真相(UnsafeCell).html"><strong aria-hidden="true">1.6.</strong> 一行代码告诉你内部可变性的真相(UnsafeCell)</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Tour_of_Rust's_Standard_Library_Traits/Tour_of_Rust's_Standard_Library_Traits.html"><strong aria-hidden="true">1.7.</strong> Tour of Rust's Standard Library Traits</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/逆变、协变与子类型，以及Rust/逆变、协变与子类型，以及Rust.html"><strong aria-hidden="true">1.8.</strong> 逆变、协变与子类型，以及Rust</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust自引用结构、Pin与Unpin/Rust自引用结构、Pin与Unpin.html"><strong aria-hidden="true">1.9.</strong> Rust自引用结构、Pin与Unpin</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/为什么Rust需要Pin,Unpin/为什么Rust需要Pin,Unpin.html"><strong aria-hidden="true">1.10.</strong> 译：为什么 Rust 需要 Pin, Unpin ？</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/定海神针Pin和Unpin/定海神针Pin和Unpin.html"><strong aria-hidden="true">1.11.</strong> 译：定海神针 Pin 和 Unpin</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/sizedness-in-rust/sizedness-in-rust.html"><strong aria-hidden="true">1.12.</strong> Sizedness in Rust</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust生命周期集大成者PhantomData〈T〉/Rust生命周期集大成者PhantomData〈T〉.html"><strong aria-hidden="true">1.13.</strong> Rust生命周期集大成者 PhantomData&lt;T&gt;</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操_Part_0.html"><strong aria-hidden="true">1.14.</strong> 数据库表达式执行的黑魔法：用Rust做类型体操 Part 0</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：GAT实现引用类型关联_Part_1.html" class="active"><strong aria-hidden="true">1.15.</strong> 数据库表达式执行的黑魔法：GAT实现引用类型关联 Part 1</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用HRTB写bound_Part_2.html"><strong aria-hidden="true">1.16.</strong> 数据库表达式执行的黑魔法：用HRTB写bound Part 2</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操之用宏展开重复代码_Part_3_&_4.html"><strong aria-hidden="true">1.17.</strong> 数据库表达式执行的黑魔法：用Rust做类型体操之用宏展开重复代码 Part 3 & 4</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：与Rust编译器斗智斗勇之表达式向量化_Part_5_&_6.html"><strong aria-hidden="true">1.18.</strong> 数据库表达式执行的黑魔法：与Rust编译器斗智斗勇之表达式向量化 Part 5 & 6</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：在Rust中用宏关联逻辑类型和实际类型_Part_7.html"><strong aria-hidden="true">1.19.</strong> 数据库表达式执行的黑魔法：在Rust中用宏关联逻辑类型和实际类型 Part 7</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">2.</strong> 生命周期</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../02_生命周期/Rust中的生命周期——从StrSplit实例说开去/Rust中的生命周期——从StrSplit实例说开去.html"><strong aria-hidden="true">2.1.</strong> Rust中的生命周期——从StrSplit实例说开去</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/与ChatGPT深度对话来学Rust生命周期/与ChatGPT深度对话来学Rust生命周期.html"><strong aria-hidden="true">2.2.</strong> 与ChatGPT深度对话来学Rust生命周期</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——early_bound与late_bound（1）/进击的Rust生命周期——early_bound与late_bound（1）.html"><strong aria-hidden="true">2.3.</strong> 进击的Rust生命周期——early_bound与late_bound（1）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——early_bound与late_bound（2）/进击的Rust生命周期——early_bound与late_bound（2）.html"><strong aria-hidden="true">2.4.</strong> 进击的Rust生命周期——early_bound与late_bound（2）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——一力降十会的MIR（1）/进击的Rust生命周期——一力降十会的MIR（1）.html"><strong aria-hidden="true">2.5.</strong> 进击的Rust生命周期——一力降十会的MIR（1）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——一力降十会的MIR（2）/进击的Rust生命周期——一力降十会的MIR（2）.html"><strong aria-hidden="true">2.6.</strong> 进击的Rust生命周期——一力降十会的MIR（2）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/Common_Rust_Lifetime_Misconceptions/Common_Rust_Lifetime_Misconceptions.html"><strong aria-hidden="true">2.7.</strong> Common Rust Lifetime Misconceptions</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/Rust生命周期常见误区/Rust生命周期常见误区.html"><strong aria-hidden="true">2.8.</strong> 译：Rust生命周期常见误区</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">3.</strong> 无畏并发</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../05_无畏并发/简单写个Rust无锁队列/简单写个Rust无锁队列.html"><strong aria-hidden="true">3.1.</strong> 简单写个Rust无锁队列</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——混合自旋锁/进击的Rust多线程——混合自旋锁.html"><strong aria-hidden="true">3.2.</strong> 进击的Rust多线程——混合自旋锁</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/An_unsafe_tour_of_Rust's_Send_and_Sync/An_unsafe_tour_of_Rust's_Send_and_Sync.html"><strong aria-hidden="true">3.3.</strong> An unsafe tour of Rust's Send and Sync</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——Send与Sync/进击的Rust多线程——Send与Sync.html"><strong aria-hidden="true">3.4.</strong> 进击的Rust多线程——Send与Sync</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——离经叛道的PhantomData/进击的Rust多线程——离经叛道的PhantomData.html"><strong aria-hidden="true">3.5.</strong> 进击的Rust多线程——离经叛道的PhantomData</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust_Async_Pin概念解析/Rust_Async_Pin概念解析.html"><strong aria-hidden="true">3.6.</strong> Rust Async: Pin概念解析</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust和C++的并发库对比/Rust和C++的并发库对比.html"><strong aria-hidden="true">3.7.</strong> 译：Rust 和 C++ 的并发库对比</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust原子类型和内存排序/Rust原子类型和内存排序.html"><strong aria-hidden="true">3.8.</strong> Rust原子类型和内存排序</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">4.</strong> 网络编程</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../06_网络编程/从编解码层面理解WebSocket_手写一个WebSocket/从编解码层面理解WebSocket_手写一个WebSocket.html"><strong aria-hidden="true">4.1.</strong> 从编解码层面理解WebSocket 手写一 个WebSocket</a></li><li class="chapter-item expanded "><a href="../../06_网络编程/透过Rust探索系统的本原：网络篇/透过Rust探索系统的本原：网络篇.html"><strong aria-hidden="true">4.2.</strong> 透过Rust探索系统的本原：网络篇</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">5.</strong> 轮子系列</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../07_轮子系列/700行Rust写一个内存分配器/700行Rust写一个内存分配器.html"><strong aria-hidden="true">5.1.</strong> 700行Rust写一个内存分配器</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/Rust：网络库的实现思路/Rust：网络库的实现思路.html"><strong aria-hidden="true">5.2.</strong> Rust：网络库的实现思路</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/Rust异步运行时基础部件/Rust异步运行时基础部件.html"><strong aria-hidden="true">5.3.</strong> Rust异步运行时基础部件</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（1）.html"><strong aria-hidden="true">5.4.</strong> 使用Rust+epoll编写异步IO框架（1）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（2）.html"><strong aria-hidden="true">5.5.</strong> 使用Rust+epoll编写异步IO框架（2）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（3）.html"><strong aria-hidden="true">5.6.</strong> 使用Rust+epoll编写异步IO框架（3）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day1.html"><strong aria-hidden="true">5.7.</strong> 用rust从零开发一套web框架：day1</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day2.html"><strong aria-hidden="true">5.8.</strong> 用rust从零开发一套web框架：day2</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day3.html"><strong aria-hidden="true">5.9.</strong> 用rust从零开发一套web框架：day3</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day4.html"><strong aria-hidden="true">5.10.</strong> 用rust从零开发一套web框架：day4</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day5.html"><strong aria-hidden="true">5.11.</strong> 用rust从零开发一套web框架：day5</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">6.</strong> 奇技淫巧</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Copy-On-Write是不是优化？/Copy-On-Write是不是优化？.html"><strong aria-hidden="true">6.1.</strong> 译：Copy-On-Write是不是优化？</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/揭秘神奇的Rust_Axum风格的函数实现/揭秘神奇的Rust_Axum风格的函数实现.html"><strong aria-hidden="true">6.2.</strong> 译：揭秘神奇的 Rust Axum 风格的函数实现</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/“变长参数”函数与回调/“变长参数”函数与回调.html"><strong aria-hidden="true">6.3.</strong> “变长参数”函数与回调</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Rust字符串格式化的幕后：format_args!()/Rust字符串格式化的幕后：format_args!().html"><strong aria-hidden="true">6.4.</strong> 译：Rust字符串格式化的幕后：format_args!()</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/给Rust带来一点C++特产/给Rust带来一点C++特产.html"><strong aria-hidden="true">6.5.</strong> 给Rust带来一点C++特产</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/一步步实现_Rust_Bevy_ECS_的_System_简化版本/一步步实现_Rust_Bevy_ECS_的_System_简化版本.html"><strong aria-hidden="true">6.6.</strong> 一步步实现 Rust Bevy ECS 的 System 简化版本</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Exploring_Design_Patterns_in_Rust_with_Algorithmic_Trading_Examples/Exploring_Design_Patterns_in_Rust_with_Algorithmic_Trading_Examples.html"><strong aria-hidden="true">6.7.</strong> Exploring Design Patterns in Rust with Algorithmic Trading Examples</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">7.</strong> 源码分析</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：bytes源码分析/Rust并发：bytes源码分析.html"><strong aria-hidden="true">7.1.</strong> Rust并发：bytes源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：标准库Arc源码分析/Rust并发：标准库Arc源码分析.html"><strong aria-hidden="true">7.2.</strong> Rust并发：标准库Arc源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：标准库sync_Once源码分析/Rust并发：标准库sync_Once源码分析.html"><strong aria-hidden="true">7.3.</strong> Rust并发：标准库sync::Once源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust源码阅读：引用计数Rc/Rust源码阅读：引用计数Rc.html"><strong aria-hidden="true">7.4.</strong> Rust源码阅读：引用计数Rc</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust源码阅读：Cell、RefCell与内部可变性/Rust源码阅读：Cell、RefCell与内部可变性.html"><strong aria-hidden="true">7.5.</strong> Rust源码阅读： Cell、RefCell与内部可变性</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/关于_Rust_的_UnsafeCell、Cell_与_RefCell/关于_Rust_的_UnsafeCell、Cell_与_RefCell.html"><strong aria-hidden="true">7.6.</strong> 关于 Rust 的 UnsafeCell、Cell 与 RefCell</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust_Async_async-stream源码分析/Rust_Async_async-stream源码分析.html"><strong aria-hidden="true">7.7.</strong> Rust Async: async-stream源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/走进Tokio的异步世界/走进Tokio的异步世界.html"><strong aria-hidden="true">7.8.</strong> 走进 Tokio 的异步世界</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/tokio.rs_runtime的实现/tokio.rs_runtime的实现.html"><strong aria-hidden="true">7.9.</strong> tokio.rs runtime 的实现</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_internals/Tokio_internals.html"><strong aria-hidden="true">7.10.</strong> Tokio internals</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_internals/译文：Tokio內部机制.html"><strong aria-hidden="true">7.11.</strong> 译：Tokio 内部机制</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust_Axum_HTTP_框架的架构分析/Rust_Axum_HTTP_框架的架构分析.html"><strong aria-hidden="true">7.12.</strong> Rust Axum HTTP 框架的架构分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/安利一个Rust_Game_Engine：Bevy--ECS部分/安利一个Rust_Game_Engine：Bevy--ECS部分.html"><strong aria-hidden="true">7.13.</strong> 安利一个Rust Game Engine：Bevy--ECS部分</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_解析之任务调度/Tokio_解析之任务调度.html"><strong aria-hidden="true">7.14.</strong> Tokio 解析之任务调度</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">8.</strong> 生态观察</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../11_生态观察/Rust_web_frameworks_have_subpar_error_reporting/Rust_web_frameworks_have_subpar_error_reporting.html"><strong aria-hidden="true">8.1.</strong> Rust web frameworks have subpar error reporting</a></li><li class="chapter-item expanded "><a href="../../11_生态观察/SeaORM：要做Rust版本的ActiveRecord/SeaORM：要做Rust版本的ActiveRecord.html"><strong aria-hidden="true">8.2.</strong> SeaORM：要做Rust版本的ActiveRecord</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">9.</strong> 死灵终极</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_总述.html"><strong aria-hidden="true">9.1.</strong> 译：Learn Rust the Dangerous Way 总述</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_0.html"><strong aria-hidden="true">9.2.</strong> 译：Learn Rust the Dangerous Way 0</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_1.html"><strong aria-hidden="true">9.3.</strong> 译：Learn Rust the Dangerous Way 1</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_2.html"><strong aria-hidden="true">9.4.</strong> 译：Learn Rust the Dangerous Way 2</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_3.html"><strong aria-hidden="true">9.5.</strong> 译：Learn Rust the Dangerous Way 3</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_4.html"><strong aria-hidden="true">9.6.</strong> 译：Learn Rust the Dangerous Way 4</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_5.html"><strong aria-hidden="true">9.7.</strong> 译：Learn Rust the Dangerous Way 5</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（一）.html"><strong aria-hidden="true">9.8.</strong> Unsafe Rust 随堂小测（一）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（二）.html"><strong aria-hidden="true">9.9.</strong> Unsafe Rust 随堂小测（二）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（三）.html"><strong aria-hidden="true">9.10.</strong> Unsafe Rust 随堂小测（三）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测参考答案.html"><strong aria-hidden="true">9.11.</strong> Unsafe Rust 随堂小测参考答案</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">Rust 优秀博文</h1>

                    <div class="right-buttons">
                        <a href="../../print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="数据库表达式执行的黑魔法gat-实现引用类型关联-part-1"><a class="header" href="#数据库表达式执行的黑魔法gat-实现引用类型关联-part-1">数据库表达式执行的黑魔法：GAT 实现引用类型关联 (Part 1)</a></h1>
<p>作者：<a href="https://www.zhihu.com/people/skyzh">迟策</a></p>
<p>原载：<a href="https://zhuanlan.zhihu.com/p/460977012">https://zhuanlan.zhihu.com/p/460977012</a></p>
<p>上篇：<a href="https://zhuanlan.zhihu.com/p/460702914">数据库表达式执行的黑魔法：用 Rust 做类型体操 (Part 0)</a></p>
<p>下篇：<a href="https://zhuanlan.zhihu.com/p/461405621">数据库表达式执行的黑魔法：用 Rust 做类型体操 (Part 2)</a></p>
<h2 id="day-1-array-与-arraybuilder"><a class="header" href="#day-1-array-与-arraybuilder">Day 1: <code>Array</code> 与 <code>ArrayBuilder</code></a></h2>
<p>如果您想直接看最终实现，可以直接跳转到 <a href="https://link.zhihu.com/?target=https%3A//github.com/skyzh/type-exercise-in-rust/tree/master/archive/day1">Day 1 对应的源代码</a>.</p>
<h3 id="目标"><a class="header" href="#目标">目标</a></h3>
<p>数据库表达式向量化执行的过程写成伪代码大概是这样：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>fn eval_binary(i1: InputArray, i2: InputArray) -&gt; OutputArray {
    let mut builder = OutputArray::Builder::new();
    for (i1, i2) in i1.iter().zip_eq(i2.iter()) {
      builder.push(sql_func(i1, i2));
    }
    builder.finish()
}
<span class="boring">}
</span></code></pre></pre>
<p>注意 <code>OutputArray::Builder::new()</code>：如果需要实现类似于上面代码的泛型 <code>eval_bianry</code>，我们的类型框架就要支持从 <code>Array</code> 推导出 <code>ArrayBuilder</code> 的类型。</p>
<p>因此，本文就介绍如何实现 <code>Array</code> 和 <code>ArrayBuilder</code> 这一对 trait，从而写出 <code>eval_binary</code> 函数体的前两行。涉及到的知识点有：</p>
<ul>
<li>Associated Type</li>
<li>Generic Associated Type</li>
</ul>
<h3 id="实现-primitivearray-与-stringarray"><a class="header" href="#实现-primitivearray-与-stringarray">实现 <code>PrimitiveArray</code> 与 <code>StringArray</code></a></h3>
<p>在这个系列中，我们会实现一套类似于 Apache Arrow 内存布局的数组结构。Array 是 <code>Option&lt;T&gt;</code> 的集合。存储定长类型的 Array 叫 <code>PrimitiveArray</code>。这种数据如果用 <code>Vec&lt;Option&lt;T&gt;&gt;</code> 存储，每个 <code>Option&lt;T&gt;</code> 所需要的内存是 <code>mem::size_of::&lt;T&gt;()</code> 加上 <code>Option</code> 一个 bit 的开销。这个 bit 由于内存对齐的原因，往往会和 <code>T</code> 一样大。举例：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>assert_eq!(std::mem::size_of::&lt;u64&gt;(), 8);
assert_eq!(std::mem::size_of::&lt;Option&lt;u64&gt;&gt;(), 16);
<span class="boring">}
</span></code></pre></pre>
<p>诸如 Apache Arrow 的存储可以大大优化 bitmap 所需要的空间。<code>PrimitiveArray</code> 使用一个 bitmap 来标识某个位置的元素是 <code>None</code> 还是有东西，用 <code>Vec&lt;T&gt;</code> 存储每一个位置的值，把 bitmap 和具体数据分开，以减少内存对齐的开销。</p>
<p><code>PrimitiveArray</code> 对于所有基本类型的实现几乎是一致的，所以我们可以直接用泛型来实现它。<code>PrimitiveType</code> 是我们自己定义的一个 trait。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub struct PrimitiveArray&lt;T: PrimitiveType&gt; {
    /// The actual data of this array.
    data: Vec&lt;T&gt;,

    /// The null bitmap of this array.
    bitmap: BitVec,
}

impl PrimitiveArray&lt;T&gt; {
    fn get(&amp;self, idx: usize) -&gt; Option&lt;T&gt; {
        if self.bitmap[idx] {
            Some(self.data[idx])
        } else {
            None
        }
    }

    fn len(&amp;self) -&gt; usize {
        self.data.len()
    }
}
<span class="boring">}
</span></code></pre></pre>
<p>Apache Arrow 对于 <code>StringArray</code> 的存储也有一定的优化。数据库系统往往会顺序扫描一个 <code>Array</code> 里面所有的 <code>String</code>。如果使用 <code>Vec&lt;Option&lt;String&gt;&gt;</code> 来存储字符串的集合，有两个问题：</p>
<ul>
<li>写入 <code>Vec&lt;Option&lt;String&gt;&gt;</code> 必须要创建一个 <code>String</code> 对象，会有内存分配的开销。在数据库的场景中，开发者往往希望能直接把网络中接收到的数据、或存储里读出来的磁盘页 <code>Vec&lt;u8&gt;</code> 零开销地转换成一个 <code>StringArray</code>；而不是把 <code>Vec&lt;u8&gt;</code> 拷一遍转换成很多很多 <code>String</code>。</li>
<li>连续读取一个 <code>Vec&lt;Option&lt;String&gt;&gt;</code> 里面的 <code>String</code> 可能对缓存不友好。<code>String</code> 是一个指针，散落在内存里的各个地方，遍历 <code>Vec&lt;Option&lt;String&gt;&gt;</code> 的过程反映到内存读取上可能是东读一块，西读一块，随机读。</li>
</ul>
<p>综上所述，<code>StringArray</code> 应该把 <code>String</code> 紧凑地存在一起。在 Apache Arrow 中，<code>StringArray</code> 分为三个部分：一个平摊的字符数组，一个记录 offset 的数组，以及一个 bitmap。比如，<code>StringArray</code> 中包含 <code>233</code>, <code>abc</code>, null 三个数据，它会以这种方式存在内存里：</p>
<pre><code class="language-text">data:    233abc
         ^  ^  ^
         |  |  |--|
offsets: 0, 3, 6, 6
bitmap: true, true, false
</code></pre>
<p>这样一来，整个 <code>StringArray</code> 所对应的数据在内存里就连续了。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub struct StringArray {
    /// The flattened data of string.
    data: Vec&lt;u8&gt;,

    /// Offsets of each string in the data flat array.
    offsets: Vec&lt;usize&gt;,

    /// The null bitmap of this array.
    bitmap: BitVec,
}

impl StringArray {
    fn get(&amp;self, idx: usize) -&gt; Option&lt;&amp;str&gt; {
        if self.bitmap[idx] {
            let range = self.offsets[idx]..self.offsets[idx + 1];
            Some(unsafe { std::str::from_utf8_unchecked(&amp;self.data[range]) })
        } else {
            None
        }
    }
<span class="boring">}
</span></code></pre></pre>
<p>开发者需要使用 <code>PrimitiveArrayBuilder</code> 构造 <code>PrimitiveArray</code>，使用 <code>StringArrayBuilder</code> 构造 <code>StringArray</code>。构造的过程和读取差不多，在这里就不赘述了，有兴趣可以直接看代码或者自己实现。</p>
<h3 id="实现-array-trait"><a class="header" href="#实现-array-trait">实现 <code>Array</code> trait</a></h3>
<p><code>Array</code> trait 囊括了整个系统中所有的 Array – <code>PrimitiveArray</code>, <code>StringArray</code>。先试着写一下它的声明：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>/// [`Array`] is a collection of data of the same type.
pub trait Array: Send + Sync + Sized + 'static {
    /// The reference item of this array.
    type RefItem;

    /// Retrieve a reference to value.
    fn get(&amp;self, idx: usize) -&gt; Option&lt;Self::RefItem&gt;;

    /// Number of items of array.
    fn len(&amp;self) -&gt; usize;

    /// Indicates whether this array is empty
    fn is_empty(&amp;self) -&gt; bool {
        self.len() == 0
    }
}
<span class="boring">}
</span></code></pre></pre>
<p>然后尝试给 <code>PrimitiveArray</code> 和 <code>StringArray</code> 实现这个 trait。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>impl&lt;T: PrimitiveType&gt; Array for PrimitiveArray&lt;T&gt; {
    type RefItem = T;
    
    // ...
}

impl Array for StringArray {
    type RefItem = &amp;str;
    
    // ...
}
<span class="boring">}
</span></code></pre></pre>
<p>接下来就出现了一些大问题：</p>
<pre><code class="language-text">error[E0106]: missing lifetime specifier
  --&gt; archive/day1/src/array/string_array.rs:29:20
   |
29 |     type RefItem = &amp;str;
   |                    ^ expected named lifetime parameter
   |
help: consider introducing a named lifetime parameter
   |
29 |     type RefItem&lt;'a&gt; = &amp;'a str;
   |                 ++++    ++
</code></pre>
<p><code>&amp;str</code> 写在关联类型中需要一个生命周期！照着编译器的提示加上生命周期。</p>
<pre><code class="language-text">impl Array for StringArray {
    type RefItem&lt;'a&gt; = &amp;'a str;
error[E0658]: generic associated types are unstable
  --&gt; archive/day1/src/array/string_array.rs:29:5
   |
29 |     type RefItem&lt;'a&gt; = &amp;'a str;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: see issue #44265 &lt;https://github.com/rust-lang/rust/issues/44265&gt; for more information
   = help: add `#![feature(generic_associated_types)]` to the crate attributes to enable
</code></pre>
<p>又一次无情被编译器打脸，编译器说要开启 “generic associated types” (GAT)，这是个啥？</p>
<p>trait 里面的 associated type 的声明，通常来说不能再有第二层 generic parameter。举例：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub trait Array: Send + Sync + Sized + 'static {
    /// The reference item of this array.
    type RefItem&lt;T&gt;;
<span class="boring">}
</span></code></pre></pre>
<p>这个 <code>&lt;T&gt;</code> 就叫 GAT，它既可以是一个具体的类型，也可以是我们这边需要的 lifetime。所以，开启 GAT 之后，就可以在这里表达 <code>Array</code> 对应的 <code>RefItem</code> 可以是 <code>'a</code> 生命周期的东西了。更新一下 <code>Array</code> 的定义：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>/// [`Array`] is a collection of data of the same type.
pub trait Array: Send + Sync + Sized + 'static {
    /// Type of the item that can be retrieved from the [`Array`]. For example, we can get a `i32`
    /// from [`Int32Array`], while [`StringArray`] produces a `&amp;str`. As we need a lifetime that is
    /// the same as `self` for `&amp;str`, we use GAT here.
    type RefItem&lt;'a&gt;: Clone + Copy + std::fmt::Debug;
    
    /// Retrieve a reference to value.
    fn get(&amp;self, idx: usize) -&gt; Option&lt;Self::RefItem&lt;'_&gt;&gt;;

    // ...
}

impl Array for StringArray {
    /// For [`StringArray`], we can only get an `&amp;str` out of it with zero overhead.
    type RefItem&lt;'a&gt; = &amp;'a str;
    
    // ...
}

impl&lt;T: PrimitiveType&gt; Array for PrimitiveArray&lt;T&gt; {
    /// For `PrimitiveType`, we can always get the value from the array with little overhead.
    /// Therefore, we do not use the `'a` lifetime here, and simply copy the value to the user when
    /// calling `get`.
    type RefItem&lt;'a&gt; = T;
    
    // ...
}
<span class="boring">}
</span></code></pre></pre>
<p>这样，我们就可以在 <code>get</code> 函数的签名里用 <code>-&gt; Option&lt;Self::RefItem&lt;'_&gt;&gt;</code> 来表达：<code>Array</code> 里面可以拿到和 <code>self</code> 生命周期相同的引用了。</p>
<p>有的朋友可能要问了，为啥这里要用 GAT，没有别的解法吗？</p>
<p>当然有！</p>
<h3 id="解法-1修改-primitivearray-的实现使用-sized-bound"><a class="header" href="#解法-1修改-primitivearray-的实现使用-sized-bound">解法 1：修改 PrimitiveArray 的实现，使用 <code>?Sized</code> bound</a></h3>
<p>现在的实现中，我们希望 <code>PrimitiveArray</code> 返回 <code>Option&lt;i32&gt;</code> 而非 <code>Option&lt;&amp;i32&gt;</code>。有的 Array 返回的东西是有生命周期的，有的没有。第一种解法就是把它们统一，不论是 <code>StringArray</code> 还是 <code>PrimitiveArray</code> 都返回 <code>Option&lt;&amp;T&gt;</code>。</p>
<p>这样一来，我们就可以这样修改 <code>Array</code> 的定义：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub trait Array: Send + Sync + Sized + 'static {
    type RefItem: ?Sized;

    /// Retrieve a reference to value.
    fn get(&amp;self, idx: usize) -&gt; Option&lt;&amp;Self::RefItem&gt;;
}

impl Array for StringArray {
    type RefItem = str;
}

impl&lt;T: PrimitiveType&gt; Array for PrimitiveArray&lt;T&gt; {
    type RefItem = T;
}
<span class="boring">}
</span></code></pre></pre>
<p>这样就可以在 trait 里面表达“<code>get</code> 返回的 <code>Self::RefItem</code> 拥有 <code>Self</code> 的生命周期”了。</p>
<p>这个做法现在在 <a href="https://link.zhihu.com/?target=https%3A//github.com/risinglightdb/risinglight/blob/main/src/array/mod.rs">RisingLight</a> 里面用到，相对来讲还是比较好用的。不过考虑到未来还有可能存类似于 <code>Json</code> 的不定长数据 (TiKV Coprocessor 里面就有 <a href="https://link.zhihu.com/?target=https%3A//github.com/tikv/tikv/blob/master/components/tidb_query_datatype/src/codec/mysql/json/mod.rs">Json 类型</a>)，但 <code>Json</code> 可能并没有 <code>str</code> 这样的 <code>!Sized</code>type 来表示不定长的数据：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub struct Json {
  ty: JsonType, // Number, String, Array, ...
  data: Vec&lt;u8&gt;
}

pub struct JsonRef&lt;'a&gt; {
  ty: JsonType, // Number, String, Array, ...
  data: &amp;'a [u8]
}
<span class="boring">}
</span></code></pre></pre>
<p>在这个场景下，就没有办法使用 <code>?Sized</code> bound 绕过 GAT 的问题了。</p>
<h3 id="解法-2给-array-带上生命周期"><a class="header" href="#解法-2给-array-带上生命周期">解法 2：给 <code>Array</code> 带上生命周期。</a></h3>
<p>我们刚刚碰到的根本问题是：<code>Array</code> trait 里面没有一个生命周期，但 <code>get</code> 返回的东西需要一个生命周期。</p>
<p>我们完全可以把 <code>Array</code> 实现在所有 Array 的引用上，而非 Array 本身。举例：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub trait ArrayRef&lt;'a&gt;: Send {
    type RefItem: 'a;

    /// Retrieve a reference to value.
    fn get(&amp;self, idx: usize) -&gt; Option&lt;Self::RefItem&gt;;
    
    // ...
}

impl &lt;'a&gt; ArrayRef&lt;'a&gt; for &amp;'a StringArray {
    type RefItem = &amp;'a str;
}
<span class="boring">}
</span></code></pre></pre>
<p>这样也可以完美解决这个问题。不过这样一来，generics function 都没法实现在有 ownership 的 Array 上面了，感觉有些奇怪，所以这个系列没这么做。</p>
<h3 id="实现-arrayiterator"><a class="header" href="#实现-arrayiterator">实现 <code>ArrayIterator</code></a></h3>
<p>有了 GAT 之后，实现 <code>ArrayIterator</code> 也非常简单了。现在我们对不同类型的 Array 都统一了 <code>Array</code>trait，因此所有 <code>Array</code> 可以用同一套 <code>Iterator</code> 实现。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>/// An iterator that iterators on any [`Array`] type.
pub struct ArrayIterator&lt;'a, A: Array&gt; {
    array: &amp;'a A,
    pos: usize,
}

impl&lt;'a, A: Array&gt; Iterator for ArrayIterator&lt;'a, A&gt; {
    type Item = Option&lt;A::RefItem&lt;'a&gt;&gt;;

    fn next(&amp;mut self) -&gt; Option&lt;Self::Item&gt; {
        if self.pos &gt;= self.array.len() {
            None
        } else {
            let item = self.array.get(self.pos);
            self.pos += 1;
            Some(item)
        }
    }
}

impl&lt;'a, A: Array&gt; ArrayIterator&lt;'a, A&gt; {
    /// Create an [`ArrayIterator`] from [`Array`].
    pub fn new(array: &amp;'a A) -&gt; Self {
        Self { array, pos: 0 }
    }
}


impl Array for StringArray {
    // ...

    fn iter(&amp;self) -&gt; ArrayIterator&lt;Self&gt; {
        ArrayIterator::new(self)
    }
}

impl&lt;T: PrimitiveType&gt; Array for PrimitiveArray&lt;T&gt; {
    // ...

    fn iter(&amp;self) -&gt; ArrayIterator&lt;Self&gt; {
        ArrayIterator::new(self)
    }
}
<span class="boring">}
</span></code></pre></pre>
<h3 id="实现-arraybuilder-trait"><a class="header" href="#实现-arraybuilder-trait">实现 <code>ArrayBuilder</code> trait</a></h3>
<p>我们给 <code>Array</code> 加上 <code>Builder</code> 这个 associated type，然后修改各个实现：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>/// [`ArrayBuilder`] builds an [`Array`].
pub trait ArrayBuilder {
    /// The corresponding [`Array`] of this [`ArrayBuilder`].
    ///
    /// Here we use associated type to constraint the [`Array`] type of this builder, so that
    /// `Self::Array::Builder == Self`. This property is very useful when constructing generic
    /// functions, and may help a lot when implementing expressions.
    type Array: Array;

    /// Create a new builder with `capacity`.
    fn with_capacity(capacity: usize) -&gt; Self;

    /// Append a value to builder.
    fn push(&amp;mut self, value: Option&lt;&lt;Self::Array as Array&gt;::RefItem&lt;'_&gt;&gt;);

    /// Finish build and return a new array.
    fn finish(self) -&gt; Self::Array;
}

pub trait Array: Send + Sync + Sized + 'static {
    /// The corresponding [`ArrayBuilder`] of this [`Array`].
    type Builder: ArrayBuilder;
    
    // ...
}

impl&lt;T: PrimitiveType&gt; Array for PrimitiveArray&lt;T&gt; {
    type Builder = PrimitiveArrayBuilder&lt;T&gt;;
    
    // ...
}

impl Array for StringArray {
    type Builder = StringArrayBuilder;
    
    // ...
}
<span class="boring">}
</span></code></pre></pre>
<p>于是非常轻松地通过了编译，成功近在眼前，回过来实现一下本文刚开始想做的事情，除了中间那个 <code>.push</code>：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>fn eval_binary&lt;I: Array, O: Array&gt;(i1: I, i2: I) -&gt; O {
    assert_eq!(i1.len(), i2.len(), &quot;size mismatch&quot;);
    let mut builder = O::Builder::with_capacity(i1.len());
    for (i1, i2) in i1.iter().zip(i2.iter()) {
    //   builder.push(sql_func(i1, i2));
    }
    builder.finish()
}
<span class="boring">}
</span></code></pre></pre>
<p>编译器无情打脸：</p>
<pre><code class="language-text">error[E0308]: mismatched types
  --&gt; archive/day1/src/array.rs:79:9
   |
73 |     fn eval_binary&lt;I: Array, O: Array&gt;(i1: I, i2: I) -&gt; O {
   |                              - this type parameter      - expected `O` because of return type
...
79 |         builder.finish()
   |         ^^^^^^^^^^^^^^^^ expected type parameter `O`, found associated type
   |
   = note: expected type parameter `O`
             found associated type `&lt;&lt;O as array::Array&gt;::Builder as array::ArrayBuilder&gt;::Array`
   = note: you might be missing a type parameter or trait bound
</code></pre>
<p>这是为什么捏？</p>
<p>仔细看一看编译器的提示信息，发现这么一句：</p>
<pre><code class="language-text">= note: expected type parameter `O`
             found associated type `&lt;&lt;O as array::Array&gt;::Builder as array::ArrayBuilder&gt;::Array`
</code></pre>
<p>编译器在这个泛型函数里没法证明 <code>O::Builder::finish</code> 的返回值就是 <code>O</code>。</p>
<p>所以我们要修改一下 trait 的声明，把 <code>Array</code> 和 <code>ArrayBuilder</code> 里面的 associated type 关联起来，让编译器知道：<code>Array</code> 的 <code>Builder</code> 的 <code>Array</code> 还是我自己。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub trait Array: Send + Sync + Sized + 'static {
    type Builder: ArrayBuilder&lt;Array = Self&gt;;
    
    // ..
}

pub trait ArrayBuilder {
    type Array: Array&lt;Builder = Self&gt;;
    
    // ...
}
<span class="boring">}
</span></code></pre></pre>
<p>于是，编译通过，day 1 结束了！您可以在 <a href="https://link.zhihu.com/?target=https%3A//github.com/skyzh/type-exercise-in-rust">type-exercise-in-rust</a> 中围观整个系统的实现。</p>
<p>上篇：<a href="https://zhuanlan.zhihu.com/p/460702914">数据库表达式执行的黑魔法：用 Rust 做类型体操 (Part 0)</a></p>
<p>下篇：<a href="https://zhuanlan.zhihu.com/p/461405621">数据库表达式执行的黑魔法：用 Rust 做类型体操 (Part 2)</a></p>
<p><em>（系列文章持续更新中，下一次更新时间看心情）</em></p>
<p>编辑于 2022-02-02 16:17</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操_Part_0.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用HRTB写bound_Part_2.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操_Part_0.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用HRTB写bound_Part_2.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
